
//3298.统计重新排列后包含另一个字符串的子字符串数目II
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        //仍然是越长越合法的模型，只需要统计word1区间中字符出现的次数即可
        int ch[128]={0};
        int count=0;  //count用于存储字符的种类
        for(auto e:word2) 
        {
            if(ch[e]==0) count++;
            ch[e]++;
        }

        int n=word1.size();
        int left=0,k=0;  //k用于存储满足的字符个数
        long long ret=0;
        int hash[128]={0};   //hash用于存储word1的各个字符个数
        for(int right=0;right<n;right++)
        {
            hash[word1[right]]++;   //入窗口
            if(hash[word1[right]]==ch[word1[right]]) k++;
            while(k==count)
            {
                if(hash[word1[left]]==ch[word1[left]]) k--;  //出窗口
                hash[word1[left++]]--;
            }
            ret+=left;   //更新答案
        }
        return ret;
    }
};